{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 3. PCA\n",
    "\n",
    "Let $u$ be a unit-length vector, $x$ any vector and $\\alpha\\in \\mathbb R$. Then \n",
    "$$ \\|x-\\alpha u\\|^2 = \\|x\\|^2- 2\\alpha \\langle x,u\\rangle + \\alpha^2.$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For fixed $x,u$ this is a quadratic expression in $\\alpha$, that takes its minimum iff $\\alpha = \\langle x,u\\rangle$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Therefore \n",
    "$$ f_u(x) = \\arg \\min_{v\\in \\mathcal V} \\|x-v\\|^2 = \\langle x,u\\rangle u.$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Hence\n",
    "$$\\begin{align*}\n",
    "\\sum_{i=1}^m\\|x^{(i)}-f_u(x^{(i)})\\|^2 &= \\sum_{i=1}^m \\|x^{(i)}\\|^2 - 2\\langle x^{(i)}, f_u(x^{(i)})\\rangle + \\|f_u(x^{(i)})\\|^2\\\\\n",
    "&= \\sum_{i=1}^m \\|x^{(i)}\\|^2 - 2\\langle x^{(i)}, \\langle x^{(i)},u\\rangle u\\rangle + \\|\\langle x^{(i)},u\\rangle u\\|^2\\\\\n",
    "&= \\sum_{i=1}^m \\|x^{(i)}\\|^2 - 2\\langle x^{(i)},u\\rangle^2 + \\langle x^{(i)},u\\rangle^2\\\\\n",
    "&=\\sum_{i=1}^m \\|x^{(i)}\\|^2 - \\langle x^{(i)},u\\rangle^2.\n",
    "\\end{align*}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We conclude that \n",
    "$$ \\arg\\min_{u:u^Tu=1}\\sum_{i=1}^m\\|x^{(i)}-f_u(x^{(i)})\\|^2 =  \\arg\\max_{u:u^Tu=1} \\sum_{i=1}^m\\langle x^{(i)},u\\rangle^2,$$\n",
    "where the right side is exactly the definition of the first principal component, i.e. the unit vector $u$ that maximizes the variance of the projections of the data."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
